import java.util.ArrayList;
import java.util.List;

public class SplitArray {

    public static void main(String[] args) {
        SplitArray splitArray = new SplitArray();
        int[] nums = {0,8,1,4};
        splitArray.splitArray(nums, 4);
    }

    int ans = Integer.MAX_VALUE;
    public int splitArray1(int[] nums, int m) {
        int n = nums.length;
        int[] sum = new int[n];
        int temp = 0;
        for (int i = 0; i < n; i++) {
            temp += nums[i];
            sum[i] = temp;
        }
        process(sum, 0, new ArrayList<>(), n, m);
        return ans;
    }

    public void process(int[] sum, int i, List<Integer> list, int n, int m) {
        if (i == n - 1 || list.size() == m - 1) {
            if (list.size() == m - 1) {
                list.add(n - 1);
                int temp = sum[list.get(0)];
                for (int j = 1; j < list.size(); j++) {
                    temp = Math.max(sum[list.get(j)] - sum[list.get(j - 1)], temp);
                }
                ans = Math.min(ans, temp);
                list.remove(list.size() - 1);
            }
            return;
        }
        process(sum, i + 1, list, n, m);
        list.add(i);
        process(sum, i + 1, list, n, m);
        list.remove(list.size() - 1);
    }

    public int splitArray2(int[] nums, int m) {
        int n = nums.length;
        int[][] dp = new int[n][m + 1];
        int sum = 0;
        for (int i = 0; i < n; i++) {
            sum += nums[i];
            dp[i][1] = sum;
        }
        for (int i = 1; i < n; i++) {
            for (int j = 2; j <= Math.min(i + 1, m); j++) {
                int min = Integer.MAX_VALUE;
                for (int k = j - 2; k < i; k++) {
                    min = Math.min(min, Math.max(dp[k][j - 1], dp[i][1] - dp[k][1]));
                }
                dp[i][j] = min;
            }
        }
        return dp[n - 1][m];
    }

    public int splitArray(int[] nums, int m) {
        int l = Integer.MIN_VALUE;
        int r = 0;
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            l = Math.max(l, nums[i]);
            r += nums[i];
        }
        while (l < r) {
            int mid = l + (r - l) / 2;
            if (binarySearch(m, nums, mid)) {
                r = mid;
            } else l = mid + 1;
        }
        return l;
    }

    public boolean binarySearch(int m, int[] nums, int target) {
        int count = 1;
        int sum = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] + sum <= target) {
                sum += nums[i];
            } else {
                sum = nums[i];
                ++count;
            }
        }
        return count <= m;
    }
}
